import java.util.ArrayList;


public class ABRNode<T extends Comparable> implements Cloneable {

	protected ABRNode<T> left;
	protected ABRNode<T> right;
	protected T data;
	
	/**
	 * Creates a tree node
	 * @param l Left tree
	 * @param r Right tree
	 * @param d Data
	 */
	public ABRNode(ABRNode<T> l, ABRNode<T> r, T d) {
		left = l;
		right = r;
		data = d;
	}
	
	public ABRNode<T> getLeft() {return left;}
	public ABRNode<T> getRight() {return right;}
	
	public void setLeft(ABRNode<T> n) {left = n;}
	public void setRight(ABRNode<T> n) {right = n;}
	
	/**
	 * Recursively clones the tree 
	 */
	public ABRNode<T> clone() {
		try {
			ABRNode<T> tmp = (ABRNode<T>)super.clone();
			if (left != null)
				tmp.setLeft(left.clone());
			if (right != null)
				tmp.setRight(right.clone());
			return tmp;
		} catch (CloneNotSupportedException e) {
			return null;
		}
	}
	
	/**
	 * Recursively compares this tree with another one
	 */
	public boolean equals(Object o) {
		ABRNode<T> other = (ABRNode<T>)o;
		if (other.data != data)
			return false;
		else
			return (left==null || left.equals(other.left)) && 
					(right==null || right.equals(other.right));  
	}
	
	/**
	 * Inserts an item at the right position
	 * @param d Data to be inserted
	 */
	public void insert(T d) {
		int cmp = d.compareTo(data); 
		if (cmp < 0) {
			if (left == null)
				left = new ABRNode<T>(null, null, d);
			else
				left.insert(d);
		}
		else if (cmp > 0) {
			if (right == null)
				right = new ABRNode<T>(null, null, d);
			else
				right.insert(d);
		}
		//FIXME what to do?
		//else data = d;
	}
	
	/**
	 * Recursively looks for d in the tree
	 * @param d Data to look for
	 * @return true if d is found
	 */
	public boolean find(T d) {
		int cmp = d.compareTo(data);
		if (d.equals(data))
			//found
			return true;
		else if (cmp<0 && left!=null)
			//maybe on the left
			return left.find(d);
		else if (cmp>0 && right!=null)
			//maybe on the right
			return right.find(d);
		else
			//can't be equal and not on the left/right
			return false;
	}
	
	/**
	 * Displays the ordered objects sequence 
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		String tmp = "";
		//left
		if (left != null)
			tmp = left.toString();
		sb.append(tmp);
		if (tmp.length() != 0)
			sb.append(",");
		//data
		sb.append(data);
		//right
		if (right != null)
			tmp = right.toString();
		else
			tmp = "";
		if (tmp.length() != 0)
			sb.append(",");
		sb.append(tmp);
		//result
		return sb.toString();
	}
	
	/**
	 * Converts the tree to an ArrayList
	 * @return ArrayList
	 */
	public ArrayList<T> toArrayList() {
		ArrayList<T> al = new ArrayList<T>();
		if (left != null)
			al.addAll(left.toArrayList());
		al.add(data);
		if (right != null)
			al.addAll(right.toArrayList());
		return al;
	}
	
	/**
	 * Extracts objects between a and b
	 * @param a Lower bound
	 * @param b Upper bound
	 * @return ArrayList of objects
	 */
	public ArrayList<T> range(Comparable<T> a, Comparable<T> b) {
		ArrayList<T> al = new ArrayList<T>();
		//left
		if (left!=null && a.compareTo(data)<=0)
			al.addAll(left.range(a, b));
		//data (manual comparison)
		if (a.compareTo(data)<=0 && data.compareTo(b)<=0)
			al.add(data);
		//right
		if (right!=null && data.compareTo(b)<=0)
			al.addAll(right.range(a, b));
		//done!
		return al;
	}
	
	/**
	 * Extracts objects between a and b
	 * @param a Lower bound
	 * @param b Upper bound
	 * @return Array of objects
	 */
	public T[] toArray(Comparable<T> a, Comparable<T> b) {
		return (T[])range(a, b).toArray();
	}
	
}
